#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream.h>
#include <mpi.h>

#include "InOut.h"
#include "TSP.h"
#include "utilities.h"
#include "timer.h"
#include "ants.h"
#include "ls.h"
#include "solution.h"

long int termination_condition_sa(void)
/*
 FUNCTION:       checks whether termination condition is met
 INPUT:          none
 OUTPUT:         0 if condition is not met, number neq 0 otherwise
 (SIDE)EFFECTS:  none
 */
{
	return ((n_tours >= max_tours) || (elapsed_time() >= max_time)
			|| (best_til_now == optimal));
}
void gen_first_tour(long int *tour, long int tour_length)
/*
 * generate initial tour simply 1..n
 *
 */
{
	int i;
	for (i = 0; i < tour_length; i++) {
		tour[i] = i;
	}
}
void get_next_tour(long int * tour, long int * new_tour, long int tour_length)
/*
 * Generate new tour by random swap two city position
 *
 */
{
	/* generate first random position */
	//srand((unsigned) time(NULL));
	long int pos1 = rand() % tour_length;
	/* generate second random position */

	long int pos2 = pos1;

	while (pos2 == pos1) {
		//srand((unsigned) time(NULL));
		pos2 = rand() % tour_length;
	}
	//printf("pos1:%li T_T pos2:%li\n",pos1,pos2);
	// create new tour equal to old tour
	int i = 0;
	for (i = 0; i < tour_length; i++) {
		new_tour[i] = tour[i];
	}
	// swap two position of new tour
	long int tmp = new_tour[pos1];
	new_tour[pos1] = new_tour[pos2];
	new_tour[pos2] = tmp;
}
float gen_rand()
/*
 * generate random float number between 0 and 1
 */
{
	return (float) rand() / RAND_MAX;
}

long int PSA(long int * tour, int myid, double temperature, double coolingRate,
		double absoluteTemperature, int chainLength)
/*
 * Main function for parallel SA
 * input is the initial tour and the id of the process
 * first temperature cooling-rate and the end temperature
 */

{
	int iteration = 0;

	long int * new_tour = new long int [n];//calloc(n, sizeof(long int));
	long int delta_distance;
	long int distance = compute_tour_length(tour);

	Solution *this_solution = new Solution[2];
	Solution *new_solution = new Solution[2];

	best_til_now = distance;

	while ((temperature > absoluteTemperature) && !termination_condition_sa()) {
		int j = 0;
		if (best_til_now > distance) {
			best_til_now = distance;
			for (int i = 0; i < n; i++) {
				best_solution.tour[i] = tour[i];
			}
		}
		for (j = 0; j < chainLength; j++) {
			get_next_tour(tour, new_tour, instance.n);
			delta_distance = compute_tour_length(new_tour) - distance;
			double bolz = exp(-(double) delta_distance / temperature);
			if ((delta_distance < 0) || (delta_distance > 0 && bolz
					> gen_rand())) {
				distance = delta_distance + distance;
				int i = 0;
				for (i = 0; i < n; i++) {
					tour[i] = new_tour[i];
				}
				//printf("best so far now = %li,^_^in iteration :%d \n",
				//		distance, iteration);
			}
			iteration++;

			// reduce all to best solution
			this_solution[0].cost = distance;
			for (int i = 0; i < n; i++) {
				this_solution[0].tour[i] = tour[i];
			}

			MPI_Allreduce(this_solution, new_solution, 1, MPI_Solution,
					MPI_SolutionMin, MPI_COMM_WORLD);
			for (int i = 0; i < n; i++) {
				tour[i] = new_solution[0].tour[i];
			}
			distance = new_solution[0].cost;
			if (iteration % 10 == 0 && myid == 0) {
				if (is_opened == 0) {
					cout << "in iteration " << iteration
							<< " the result in process rank : " << myid
							<< " is :" << distance << " \t and the best is :"
							<< best_til_now << "\t at temperature :"
							<< temperature << "\t time taken :"
							<< elapsed_time() << "\n ";

					cout.flush();
				} else {
					out_stream << "in iteration " << iteration
							<< " the result in process rank : " << myid
							<< " is :" << distance << " \t and the best is :"
							<< best_til_now << "\t at temperature :"
							<< temperature << "\t time taken :"
							<< elapsed_time() << "\n ";

					out_stream.flush();
				}

			}
		}

		temperature *= coolingRate;

		if (max_time < elapsed_time()) {
			break;
		}

	}
	best_solution.cost = distance;
	for (int i = 0; i < n; i++) {
		best_solution.tour[i] = tour[i];
	}
	return distance;
}

long int SA(long int * tour, double temperature, double coolingRate,
		double absoluteTemperature, int chainLength)
/*
 * Main function for parallel SA
 * input is the initial tour and the id of the process
 * first temperature cooling-rate and the end temperature
 */
{
	long int iteration = 0;
	long int * new_tour = new long int [n];//calloc(n, sizeof(long int));
	long int delta_distance;
	long int distance = compute_tour_length(tour);
	best_til_now = distance;

	while ((temperature > absoluteTemperature) && !termination_condition_sa()) {
		int j = 0;
		if (best_til_now > distance) {
			best_til_now = distance;
			for (int i = 0; i < n; i++) {
				best_solution.tour[i] = tour[i];
			}
		}
		for (j = 0; j < chainLength; j++) {
			get_next_tour(tour, new_tour, instance.n);
			delta_distance = compute_tour_length(new_tour) - distance;
			double bolz = exp(-(double) delta_distance / temperature);
			if ((delta_distance < 0) || (delta_distance > 0 && bolz
					> gen_rand())) {
				distance = delta_distance + distance;
				int i = 0;
				for (i = 0; i < n; i++) {
					tour[i] = new_tour[i];
				}

			}
			iteration++;
			if (iteration % 10 == 0) {
				if (is_opened == 0) {
					cout << "in iteration " << iteration << " the result is :"
							<< distance << "\t the best is :" << best_til_now
							<< "\t at temperature :" << temperature
							<< "\t time taken :" << elapsed_time() << "\n ";
					cout.flush();
				} else {
					out_stream << "in iteration " << iteration
							<< " the result is :" << distance
							<< "\t the best is :" << best_til_now
							<< "\t at temperature :" << temperature
							<< "\t time taken :" << elapsed_time() << "\n ";
					out_stream.flush();
				}
			}
		}

		temperature *= coolingRate;
		if (max_time < elapsed_time()) {
			break;
		}
	}
	best_solution.cost = distance;
	for (int i = 0; i < n; i++) {
		best_solution.tour[i] = tour[i];
	}
	return distance;

}

long int P_Anneal(int argc, char *argv[])
/*
 *	main routine for parallel SA
 */
{

	int myid, numprocs;
	// Init MPI environment
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &myid);

	construct_datatypes();

	long int * tour = new long int [n];//calloc(n, sizeof(long int));

	gen_first_tour(tour, n);
	long int first_distance = compute_tour_length(tour);
	long int distance = PSA(tour, myid, first_distance, 0.9999, 0.00001, 5);

	MPI_Finalize();
	return distance;
}
long int Anneal(int argc, char *argv[])
/*
 *	main routine
 */
{

	long int * tour = new long int [n];//calloc(n, sizeof(long int));

	gen_first_tour(tour, n);
	long int first_distance = compute_tour_length(tour);
	long int distance = SA(tour, first_distance, 0.9999, 0.00001, 10);
	return distance;
}

int SA_main(int argc, char *argv[]) {
	/*
	 FUNCTION:       main control for running the ACO algorithms
	 INPUT:          none
	 OUTPUT:         none
	 (SIDE)EFFECTS:  none
	 COMMENTS:       this function controls the run of "max_tries" independent trials

	 */

	long int i;

	start_timers();

	seed = (long int) time(NULL);

	instance.nn_list = compute_nn_lists();
	pheromone = generate_double_matrix(n, n);
	total = generate_double_matrix(n, n);

	time_used = elapsed_time();
	if (is_opened == 0) {
		cout << "The SA has been chosen.\n" << endl;
		cout << "Initialization took %.10f seconds\n" << time_used << endl;
	} else {
		out_stream << "The SA has been chosen.\n" << endl;
		out_stream << "Initialization took %.10f seconds\n" << time_used
				<< endl;
	}

	Anneal(argc, argv);
	if (is_opened == 0) {
		cout << "the best goes here :" << best_til_now << endl;
		cout << "total time is :" << elapsed_time() << endl;
	} else {
		out_stream << "the best goes here :" << best_til_now << endl;
		out_stream << "total time is :" << elapsed_time() << endl;
	}

	//exit_program();

	return (0);
}
int PSA_main(int argc, char *argv[]) {
	/*
	 FUNCTION:       main control for running the ACO algorithms
	 INPUT:          none
	 OUTPUT:         none
	 (SIDE)EFFECTS:  none
	 COMMENTS:       this function controls the run of "max_tries" independent trials

	 */

	long int i;

	start_timers();

	seed = (long int) time(NULL);

	instance.nn_list = compute_nn_lists();
	pheromone = generate_double_matrix(n, n);
	total = generate_double_matrix(n, n);

	time_used = elapsed_time();
	if (is_opened == 0) {
		cout << "The PSA has been chosen.\n" << endl;
		cout << "Initialization took %.10f seconds\n" << time_used << endl;
	} else {
		out_stream << "The PSA has been chosen.\n" << endl;
		out_stream << "Initialization took %.10f seconds\n" << time_used
				<< endl;
	}

	P_Anneal(argc, argv);
	if (is_opened == 0) {
		cout << "the best goes here :" << best_til_now << endl;
		cout << "total time is :" << elapsed_time() << endl;
	} else {
		out_stream << "the best goes here :" << best_til_now << endl;
		out_stream << "total time is :" << elapsed_time() << endl;
	}
	//exit_program();


	return (0);
}

